Paper 2014/674

Efficient RAM and control flow in verifiable outsourced computation

Riad S. Wahby, Srinath Setty, Max Howald, Zuocheng Ren, Andrew J. Blumberg, and Michael Walfish

Abstract

Recent work on proof-based verifiable computation has resulted in built systems that employ tools from complexity theory and cryptography to address a basic problem in systems security: allowing a local computer to outsource the execution of a program while providing the local computer with a guarantee of integrity and the remote computer with a guarantee of privacy. However, support for programs that use RAM and control flow has been problematic. State of the art systems either restrict the use of these constructs (e.g., requiring static loop bounds), incur sizeable overhead on every step, or pay tremendous costs when the constructs are invoked. This paper describes Buffet, a built system that solves these problems by providing inexpensive "a la carte" RAM and dynamic control flow. Buffet composes an elegant prior approach to RAM with a novel adaptation of techniques from the compilers literature. Buffet allows the programmer to express programs in an expansive subset of C (disallowing only "goto" and function pointers), can handle essentially any example in the verifiable computation literature, and achieves the best performance in the area by multiple orders of magnitude.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. NDSS 2015
DOI
10.14722/ndss.2015.23097
Keywords
implementationapplications of PCPszero knowledgeverifiable computation with statezero-knowledgesuccinct argumentscomputationally-sound proofs
Contact author(s)
rsw @ cs nyu edu
History
2015-07-24: last of 8 revisions
2014-08-29: received
See all versions
Short URL
https://ia.cr/2014/674
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/674,
      author = {Riad S.  Wahby and Srinath Setty and Max Howald and Zuocheng Ren and Andrew J.  Blumberg and Michael Walfish},
      title = {Efficient {RAM} and control flow in verifiable outsourced computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/674},
      year = {2014},
      doi = {10.14722/ndss.2015.23097},
      url = {https://eprint.iacr.org/2014/674}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.